The present invention generally relates to an improved automatic routing method utilized for designing an LSI through routing. More particularly, the present invention relates to an improved routing method for eliminating design rule errors by removing/re-routing and to an improved method for searching for wiring routes. Specifically, the present invention searches for wiring routes by applying a maze algorithm to a wiring region divided into a plurality of grids. In particular, the method of the present invention is adapted to search for a wiring route satisfying a constraint applied on the height or the lateral width of a wiring region irrespective of the number of grids of the wiring region.
Removing/re-routing is a conventionally known routing method attaining satisfactory results. In accordance with this re-routing method, if one of the wires already routed prevents a predetermined net from being routed, then the wire is removed, the predetermined net is routed and the wire removed is re-routed.
Such a re-routing method is disclosed, for example, by Youn-Long Lin et al., "A Detailed Router Based on Simulated Evolution", 1988 International Conference on Computer Aided Design, in which design rule errors (i.e., shortcircuit of a wire) resulted from initial routing is eliminated by removing/re-routing. Hereinafter, the processing procedure of this conventional method will be described.
First, in order to meet a given hardwiring request, initial routing is performed independently on respective nets. That is to say, wiring routes are once determined without taking design rule errors caused with other wiring routes into consideration. In the above-described document, initial routing is carried out in accordance with a greedy algorithm by moving a column from left to right.
Next, if no design rule errors exist in any of the currently routed wires, then it is determined that the routing process should end. However, if any obstructive wire causing a design rule error exists, then the wire is extracted as a wire to be removed. Specifically, this extraction step is performed in the following manner.
First, the score of a net is evaluated by the following Equation 1: EQU Score of net=a.times.(number of design rule errors)+b.times.(number of contacts-number of terminals)+c.times.(real wire length/estimated wire length) (1)
(where a, b and c are parameters) PA1 (where a, b and c are also parameters)
the "estimated wire length" is herein equal to one half of the entire peripheral length of a minimum rectangle surrounding a plurality of terminals to be interconnected.
Thereafter, it is determined based on a comparison between the score of a net and a random number whether or not the net should be removed. For example, if the net has a score larger than the random number, then the net is extracted as a wire to be removed.
Subsequently, the extracted wire is removed, a target net is routed and then the wire removed is re-routed.
On the other hand, a maze algorithm has conventionally been used for searching for a route interconnecting a plurality of terminals. Such a maze algorithm is disclosed, for example, by Frank Rubin et al., "The Lee Path Connection Algorithm", 1974 IEEE Transactions on Computers, Vol. c-23, No.9. In accordance with this maze algorithm, a wiring route cost given by the following Equation 2 is used: EQU Wiring route cost=a.times.(wire length)+b.times.(number of contacts)+c.times.(number of design rule errors) (2)
If a cost regarding a design rule error is defined for a wiring route cost in accordance with Equation 2, then the design rule errors can be gradually eliminated by repeatedly performing removing/re-routing.
In recent years, in order to enhance the performance of a MOSFET, fabrication technologies for reducing the diffusion resistance of the MOSFET by utilizing silicide and/or salicide process techniques have been commonly used. Before such fabrication technologies were developed, source/drain electrodes 81 and 82 of a conventional MOSFET with high diffusion resistance shown in FIG. 9(a), including gate, source and drain electrodes 80, 81 and 82, had to be extended as metal wires 71 from a diffusion region 70 via a large number of contacts 72. However, since the diffusion resistance of a MOSFET is reduced by utilizing such fabrication technologies, the number of contacts 72 in the source/drain electrodes 81 and 82 can be considerably reduced as shown in FIG. 9(b). Thus, as can be understood from FIG. 9(b), source/drain terminals 71A and 71B, each having a small number (e.g., one in FIG. 9(b)) of contacts 72, may be formed at any arbitrary positions in the source/drain regions.
The present inventors carried out intensive analysis on an automatic routing/designing method of an LSI, in view of such progress in fabrication technologies. And we paid special attention to the fact that if the positions of the source/drain terminals 71A and 71B are appropriately moved within the source/drain regions, then a metal wire 71C can be placed over a part of the diffusion region 70 where the source/drain terminals 71A and 71B are not placed as shown in FIG. 9(b). From this point of view, we found that if the presence of freely movable terminals within a certain region is taken into consideration and if the freely movable terminals are appropriately placed in accordance with the situations of surrounding wires, then high-density routing results can be obtained.
However, according to the conventional removing/re-routing method, the positions of terminals are fixed and therefore cannot be appropriately moved in accordance with the situations of wires.
An exemplary conventional method for searching for wiring routes in accordance with the maze algorithm as disclosed by Frank Rubin et al. in the above-identified document will be described with reference to the flow chart illustrated in FIG. 24.
First, in Step S10, hardwiring information is input. Next, in Step S20, currently searchable grids are extracted. Searchable grids adjacent to a grid in a list L, i.e., available grids other than grids specified as being located in a wiring forbidden region and grids in which terminals are located, are put into a list L1. At the same time, search directions from the grid in the list L to the respective searchable grids are saved. The grids in the list L1 are extracted as searchable grids.
Then, in Step S40, wire length costs are added while the searchable grids, extracted in Step S20, are being searched for. Every time one grid is passed, a wire length cost of "1" is added. Next, a particular grid having a minimum cost is selected from the grids in the list L1 and inserted into the list L.
Subsequently, in Step S50, it is determined whether or not an end point has been reached. If the end point has been reached, then the process advances to the next step. Otherwise, the process returns to Step S20. In other words, if a grid to be reached is included among the grids in the list L, then the process advances to the next Step S60 of selecting a route having a minimum cost. Otherwise, the process returns to Step S20.
In Step S60, a wiring route having a minimum cost is extracted by tracing back the route using the search directions saved in Step S20.
Hereinafter, this process will be described in more detail with reference to FIG. 25. Herein, the number of wiring layers is assumed to be one for the sake of simplicity. A wiring region 20 is divided into a large number of grids 30. In the wiring region 20, terminals 10A, 10a, 10B, 10b, 10C and 10c and a wiring forbidden region 21 are present.
In Step S10, hardwiring information is input. The numerals of the terminals 10A, 10a, 10B, 10b, 10C and 10c denote the number of respective nets and a pair of terminals having the same number (e.g., the terminals 10A and 10a) should be hardwired to each other.
A case of routing Net 1 will be described. The start point of Net 1 is the terminal 10A and the end point thereof is the terminal 10a. In Step S20, the grid where the start point 10A is placed is first put into the list L. Then, searchable grids adjacent to the start point 10A are put into the list L1. In this example, four grids vertically and horizontally adjacent to the start point 10A are put into the list L1. At the same time, the search directions indicated by the arrows in FIG. 25 are saved. And the four grids in the list L1 are extracted as searchable grids.
Next, in Step S40, every time a single grid has been passed, a wire length cost of "1" is added.
Then, at least one grid having a minimum cost is/are selected from the list L1 and inserted into the list L. Since all of the four grids currently present in the list L1 have the same cost of "1", all these four grids are inserted into the list L.
Subsequently, if it is determined that the end point grid 10a has not been reached yet in Step S50, then the process returns to Step S20. Thereafter, until the end point grid 10a is reached, the same processing steps S20, S40 and S50 are repeatedly performed.
In FIG. 25, the numbers in respective grids represent the results obtained by adding the wire length costs.
If it is determined in Step S50 that the end point grid 10a is included in the list L after the same steps have been repeatedly performed several times, then the search direction represented by the arrows in FIG. 25 is traced back from the end point grid 10a in Step S60, thereby extracting a wiring route 40 having a minimum cost.
The routing results are illustrated in FIG. 26(a). FIG. 26(b) illustrates the results obtained by compacting downward the wires shown in FIG. 26(a). By performing compaction, not only wires but also terminals and a wiring forbidden region can be moved downward if there are vacant spaces. Thus, the terminals 10A and 10c have been moved downward.
In accordance with a conventional method for searching for wiring routes, if routing is performed in a wiring region divided into a number of grids and if the number is not sufficiently large, then wires already routed sometimes prevent routing. Thus, in order to complete routing, grids should be added from an initial stage or after it is determined that routing cannot be completed and thereby a sufficient number of grids should be secured.
However, if some constraint on height or lateral width is given to a wiring region, the constraint sometimes cannot be satisfied because of such posterior insertion of additional grids. An exemplary case will be described with reference to FIGS. 27 through 29. In the following description, a method for routing and designing a standard cell, applicable to designing an ASIC, will be exemplified.
In FIGS. 27 through 29, a height constraint 101 is ordinarily given to a standard cell 100. In the cell 100, transistors 50A, 50B, terminals 10 and power supply lines 60 are present. Herein, even though the cell actually has a multi-layer wiring structure, only wires in the first layer (a first metal wiring layer 71 for a standard cell) are illustrated for the sake of simplicity.
In FIG. 27, a grid gap 32 is defined by uniformly dividing the cell by the routing pitch of the first wiring layer 71. If maze routing is completed on the grids having a uniform routing pitch, then the height constraint on a cell can be automatically satisfied. In other words, in order to complete routing between the transistors 50A and 50B, a gap corresponding to the wires passing therethrough should be provided beforehand between the transistors.
However, it is very difficult to precisely estimate the gap before the routing is performed. In actuality, during routing and designing manually, trials and errors are inevitable for routing wires and adjusting the gap between transistors simultaneously.
For example, if the gap between the transistors 50A and 50B, obtained by pre-routing estimation, is too narrow as shown in FIG. 28, then routing fails or cannot be completed because of the shortage in number of grids. As can be seen, the terminals 10A and 10B cannot be routed because of the shortage in number of grids.
In order to solve such a problem, in accordance with a conventional method, grids having a height narrower than the routing pitch, i.e., grids having a gap 32B narrower than an ordinary gap 32A, are provided between the transistors 50A and 50B as shown in FIG. 29, thereby completing routing. Thereafter, the gap between the transistors and the gap between the wires are modified through compaction, thereby obtaining the same results as those illustrated in FIG. 27.
However, if such grids as having the narrower gap 32B are inserted as shown in FIG. 29, then the number of grids in the height direction increases. Thus, in accordance with such a conventional wiring route search method involving the insertion of narrower grids, the height constraint on the cell 100 cannot be satisfied. In the foregoing example, a case where a height constraint cannot be satisfied has been described. A similar problem happens in the same way when a constraint is given on a lateral width.